/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/5/15
 */
public class _28_52_NQueensII {


    private int n;
    private int count;
    public int eraseHigh1;

    public int totalNQueens(int n) {
        if (n < 1) return 0;
        this.n = n;
        this.eraseHigh1 = (1 << n) - 1;
        if (n < 1) return 0;
        dfs(0, 0, 0, 0);
        return count;
    }

    private void dfs(int row, int cols, int pie, int na) {
        if (row >= n) {
            ++count;
            return;
        }
        int bits = (~(cols | pie | na)) & eraseHigh1;
        while (bits > 0) {
            int p = bits & -bits;
            dfs(row + 1, cols | p, (pie | p) << 1, (na | p) >> 1);
            bits &= bits - 1;
        }
    }

    public static void main(String[] args) {
        System.out.println(new _28_52_NQueensII().totalNQueens(4));
    }
}
